#pragma once

#include<vector>
#include<iostream>
#include<functional>

//仿函数/函数对象
template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

namespace xyx
{
	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	private:
		//大堆
		void adjustDown(int parent)
		{
			Compare com;
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				//找左右孩子较大的那个
				if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
					child++;
				
				//孩子节点比父亲大就交换
				if (com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void adjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;

			while (child > 0)
			{
				if (com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

	public:
		priority_queue()
		{}
		~priority_queue()
		{}

		template<class InputIterator>
		priority_queue(InputIterator start, InputIterator last)
		{
			while (start != last)
			{
				_con.push_back(*start);
				++start;
			}

			//向下调整建堆
			//(_con.size() - 1 - 1) / 2(_con.size() - 1 - 1) / 2 就是第一个非叶子节点
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjustDown(i);
			}

		}

		void push(const T& data)
		{
			_con.push_back(data);
			adjustUp(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjustDown(0);
		}

		const T& top()
		{
			return _con[0];
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

	private:
		Container _con;
	};

	class Date
	{
	public:
		Date(int year = 1900, int month = 1, int day = 1)
			: _year(year)
			, _month(month)
			, _day(day)
		{}
		bool operator<(const Date& d)const
		{
			return (_year < d._year) ||
				(_year == d._year && _month < d._month) ||
				(_year == d._year && _month == d._month && _day < d._day);
		}
		bool operator>(const Date& d)const
		{
			return (_year > d._year) ||
				(_year == d._year && _month > d._month) ||
				(_year == d._year && _month == d._month && _day > d._day);
		}
		friend ostream& operator<<(ostream& _cout, const Date& d)
		{
			_cout << d._year << "-" << d._month << "-" << d._day;
			return _cout;
		}
	private:
		int _year;
		int _month;
		int _day;
	};

	struct GreaterPDate
	{
		bool operator()(const Date* p1, const Date* p2)
		{
			return *(p1) < *(p2);
		}
	};

	void TestPriorityQueue()
	{
		//// 大堆，需要用户在自定义类型中提供<的重载
		//priority_queue<Date> q1;
		//q1.push(Date(2018, 10, 29));
		//q1.push(Date(2018, 10, 28));
		//q1.push(Date(2018, 10, 30));
		//cout << q1.top() << endl;
		// 
		// 如果要创建小堆，需要用户提供>的重载
		priority_queue<Date*, vector<Date*>, GreaterPDate> q2;
		q2.push(new Date(2018, 10, 29));
		q2.push(new Date(2018, 10, 28));
		q2.push(new Date(2018, 10, 30));

		while (!q2.empty())
		{
			cout << *(q2.top()) << " ";
			q2.pop();
		}
	}
	
	void testpq_01()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		xyx::priority_queue<int, vector<int>> pq(v.begin(), v.end());

		while (!pq.empty())
		{
			std::cout << pq.top() << " ";
			pq.pop();
		}
	}
}